/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Grafo;

import Exceptions.ArestaJaExisteException;
import Exceptions.ArestaNulaException;
import Exceptions.VerticeJaExisteException;
import Exceptions.VerticeNuloException;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class GrafoLista implements Graph {

   LinkedList<Vertice> vertices;
    LinkedList<LinkedList<Aresta>> arestas;

    public GrafoLista() {
        vertices = new LinkedList();
        arestas = new LinkedList();
    }

    public Vertice buscarVertice(String name) {
        Vertice retorno = null;
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices.get(i).getNome().equals(name)) {
                retorno = vertices.get(i);
            }
        }
        return retorno;
    }

    public int buscarPosicaoVertice(String name) {
        int retorno = -1;
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices.get(i).getNome().equals(name)) {
                retorno = i;
            }
        }
        return retorno;
    }

    public boolean existeVertice(String name) {
        return (buscarVertice(name) != null);
    }

    @Override
    public void inserirVertice(Vertice vertice) throws VerticeJaExisteException {
        if (!existeVertice(vertice.getNome())) {
            vertices.add(vertice);
            arestas.add(new LinkedList());
        } else {
            //System.out.println("Vértice já existe");
            throw new VerticeJaExisteException();
        }
    }

    public void inserirAresta(Aresta aresta) throws ArestaNulaException   {
        int posicaoOrigem = buscarPosicaoVertice(aresta.getOrigem().getNome());
        int posicaoDestino = buscarPosicaoVertice(aresta.getDestino().getNome());
        if (posicaoOrigem != -1 && posicaoDestino != -1) {
            arestas.get(posicaoOrigem).add(aresta);
        } else {
            System.out.println("Par de vértices não existe");
            throw new ArestaNulaException();
        }
    }

   public void setVisited(String name)
   {
       
       vertices.get(this.buscarPosicaoVertice(name)).isVisited = true;
   }

   

    public Iterator<Aresta> obterArestas() {
        LinkedList<Aresta> arestas = new LinkedList();
        Iterator<Aresta> arestasIterador;
        for (int i = 0; i < vertices.size(); i++) {
            arestasIterador = this.arestas.get(i).iterator();
            while (arestasIterador.hasNext()) {
                arestas.add(arestasIterador.next());
            }
        }
        return arestas.iterator();
    }

    @Override
    public void acceptVisitor(Visitor visitor) {

        for (int i = 0; i < vertices.size(); i++) {
            recuperarVertices().get(i).acceptVisitor(visitor);
        }

        System.out.println("Todos os amigos foram visitados");
    }
    
    //já funciona
    @Override
    public LinkedList<Vertice> breadthFirstTraversal(Visitor visitor, int start) {
        
        System.out.println("\nIniciando visita em largura");
             
        Queue <Vertice> queue = new LinkedList <Vertice>();
         LinkedList <Vertice> retorno = new LinkedList <Vertice>();
        queue.add(this.vertices.get(start));
        retorno.add(this.vertices.get(start));
        
        while (!queue.isEmpty()) {

            Vertice vertice = (Vertice)queue.remove();
            
            vertice.acceptVisitor(visitor);
            retorno.add(vertice);
            setVisited(vertice.getNome());
          
            
            LinkedList <Vertice> sucessors = vertice.getAdjacentes();
          
            for(int j=0; j<sucessors.size();j++){
                
                Vertice next = sucessors.get(j);
                  
                if (!next.isVisited){
                    setVisited(vertice.getNome());
              
                    queue.add(next);
                }
            }
            
        }
        return retorno;
    }
    
    
    //@TODO to be fixed yet
    @Override
    public LinkedList <Vertice> dephFirstTraversal(Visitor visitor, int start) {
        
        System.out.println("Iniciando visita em profundidade");
        
        boolean[] visited = new boolean[this.vertices.size()];
        LinkedList <Vertice> retorno = new LinkedList <Vertice>();
          vertices.get(0).acceptVisitor(visitor);
        retorno.add(vertices.get(0));
        for (int v = 0; v < vertices.size(); ++v) {

            dephFirstTraversal(visitor, vertices.get(v), retorno);

        }
        return retorno;
    }

    private void dephFirstTraversal(Visitor visitor, Vertice vertice,LinkedList <Vertice> retorno) {

        
        vertice.isVisited = true;
      
        for (int i = 0; i < vertice.getArestas().size(); i++) {
            Vertice to = vertice.getAdjacentes().get(i);
            
            if (!to.isVisited) {
                to.acceptVisitor(visitor);
               
               retorno.add(to);
                dephFirstTraversal(visitor, to, retorno);
            }
        }
    }

   

    @Override
    public boolean existeAresta(Aresta aresta) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public boolean existeVertice(Vertice vertice) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public LinkedList<Vertice> menorCaminho(Vertice origem, Vertice destino) throws VerticeNuloException {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public LinkedList<Vertice> recuperarVertices() {
        return vertices;
    }
}
